﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Inspired.Euler
{
    /// <summary>
    /// A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. 
    /// For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, 
    /// which means that 28 is a perfect number.
    /// 
    /// A number n is called deficient if the sum of its proper divisors is less than n
    /// and it is called abundant if this sum exceeds n.
    /// 
    /// As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, 
    /// the smallest number that can be written as the sum of two abundant numbers is 24.
    /// By mathematical analysis, it can be shown that all integers greater than 28123 can be written as
    /// the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis
    /// even though it is known that the greatest number that cannot be expressed as the sum of two abundant
    /// numbers is less than this limit.
    /// 
    /// Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
    /// </summary>
    public static class Problem023
    {
        static void Main()
        {
            int top = 28123;
            long result = 0;
            long[] numbers = new long[top];
            List<long> abundants = new List<long>();

            foreach (long i in Enumerable.Range(0, top))
            {
                result += i;
                if (i.Divisors().Where(n => n < i).Sum() > i)
                    abundants.Add(i);
            }

            Dictionary<long, object> no = new Dictionary<long, object>();
            for (int x = 0; x < abundants.Count; x++)
            {
                for (int y = x; y < abundants.Count; y++)
                {
                    long value = abundants[x] + abundants[y];
                    if (value < top && !no.ContainsKey(value))
                    {
                        result -= value;
                        no.Add(value, null);
                    }
                }
            }


            result.DisplayAndPause(); //4179871
        }
    }
}
